#include <iostream>
#include <vector>
#include <functional>
using namespace std;

auto swapVector = [](vector<int> &arr, int i, int j)
{
    //临时变量交换
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    //加法交换
    // arr[j] = arr[i] + arr[j];
    // arr[i] = arr[j] - arr[i];
    // arr[j] = arr[j] - arr[i];
    //减法交换
    // arr[j] = arr[i] - arr[j];
    // arr[i] = arr[i] - arr[j];
    // arr[j] = arr[i] + arr[j];
    //异或交换
    // arr[j] = arr[i] ^ arr[j];
    // arr[i] = arr[i] ^ arr[j];
    // arr[j] = arr[i] ^ arr[j];
};

void sort_1(vector<int> &arr);
void sort_2(vector<int> &arr);
void sort_3(vector<int> &arr);

int main()
{
    vector<int> arr = {6, 2, 1, 3, 5, 4};

    function<void(vector<int> &)> output = [](vector<int> &arr)
    {
        int length = arr.size();
        for (int i = 0; i < length; ++i)
        {
            cout << arr[i] << " ";
        }
        cout << endl;
    };

    vector<int> temp(arr);
    output(temp);
    sort_1(temp);
    output(temp);
    temp.clear();
    temp = arr;
    output(temp);
    sort_2(temp);
    output(temp);
    temp.clear();
    temp = arr;
    output(temp);
    sort_3(temp);
    output(temp);
    return 0;
}

void sort_1(vector<int> &arr)
{
    int length = arr.size();
    for (int i = 0; i < length - 1; ++i)
    {
        for (int j = 0; j < length - 1 - i; ++j)
        {
            if (arr[j] > arr[j + 1])
                swapVector(arr, j, j + 1);
        }
    }
}

void sort_2(vector<int> &arr)
{
    int length = arr.size();
    bool swapped = true;
    for (int i = 0; i < length - 1; ++i)
    {
        if (!swapped)
            break;
        swapped = false;
        for (int j = 0; j < length - 1 - i; ++j)
        {
            if (arr[j] > arr[j + 1])
            {
                swapVector(arr, j, j + 1);
                swapped = true;
            }
        }
    }
}

void sort_3(vector<int> &arr)
{
    int length = arr.size();
    bool swapped = true;
    int lastNotChanged = length - 1;
    while (swapped)
    {
        swapped = false;
        int index = -1;
        for (int i = 0; i < lastNotChanged; ++i)
        {
            if (arr[i] > arr[i + 1])
            {
                swapVector(arr, i, i + 1);
                swapped = true;
                index = i;
            }
        }
        lastNotChanged = index;
    }
}
